package main

import "fmt"

/**
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
*/

//type interval struct {
//	start, end int
//}
//
//func main() {
//	fmt.Println("Hello World")
//	arr := []interval{
//		interval{start: 1, end: 3},
//		interval{start: 2, end: 6},
//		interval{start: 8, end: 10},
//		interval{start: 7, end: 9},
//		interval{start: 20, end: 25},
//		interval{start: 22, end: 23},
//		interval{start: 30, end: 31},
//		interval{start: 29, end: 32},
//	}
//	fmt.Println("输入：", arr)
//
//	resarr := merge(arr)
//	fmt.Println("输出：", resarr)
//}
//
//func merge(arr []interval) []interval {
//	res := make([]interval, 0, len(arr))
//	for _, v1 := range arr {
//		if len(res) == 0 {
//			res = append(res, v1)
//			fmt.Println(res)
//		} else {
//			f := true
//			for i, v2 := range res {
//				if v2.start >= v1.start && v2.start < v1.end && v2.end >= v1.end {
//					v2.start = v1.start
//					//v2.end = v2.end
//					res[i] = v2
//					f = false
//					break
//				} else if v2.start <= v1.start && v2.end >= v1.end {
//					f = false
//					break
//				} else if v2.start <= v1.start && v2.end > v1.start && v2.end <= v1.end {
//					//v2.start = v2.start
//					v2.end = v1.end
//					res[i] = v2
//					f = false
//					break
//					//v2.end = v1.start
//				} else if v2.start >= v1.start && v2.end <= v1.end {
//					v2.start = v1.start
//					v2.end = v1.end
//					res[i] = v2
//					f = false
//					break
//				}
//			}
//			if f {
//				res = append(res, v1)
//			}
//		}
//	}
//	return res
//}

type interval struct {
	start, end int
}

func main() {
	fmt.Println("Hello World")
	arr := []*interval{
		&interval{start: 1, end: 3},
		&interval{start: 2, end: 6},
		&interval{start: 8, end: 10},
		&interval{start: 7, end: 9},
		&interval{start: 20, end: 25},
		&interval{start: 22, end: 23},
		&interval{start: 30, end: 31},
		&interval{start: 29, end: 32},
	}
	fmt.Println("输入：", arr)

	resarr := merge(arr)
	fmt.Println("输出：", resarr)
}

func merge(arr []*interval) []interval {
	res := make([]interval, 0, len(arr))
	for _, v1 := range arr {
		if len(res) == 0 {
			res = append(res, *v1)
			fmt.Println(res)
		} else {
			f := true
			for i, v2 := range res {
				if v2.start >= v1.start && v2.start < v1.end && v2.end >= v1.end {
					v2.start = v1.start
					//v2.end = v2.end
					res[i] = v2
					f = false
					break
				} else if v2.start <= v1.start && v2.end >= v1.end {
					f = false
					break
				} else if v2.start <= v1.start && v2.end > v1.start && v2.end <= v1.end {
					//v2.start = v2.start
					v2.end = v1.end
					res[i] = v2
					f = false
					break
					//v2.end = v1.start
				} else if v2.start >= v1.start && v2.end <= v1.end {
					v2.start = v1.start
					v2.end = v1.end
					res[i] = v2
					f = false
					break
				}
			}
			if f {
				res = append(res, *v1)
			}
		}
	}
	return res
}
